﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GameBaseCode
{
    public struct Node
    {
        public NODE_STATE state;
        public int cost;
        public bool isOpen;
    };

    public enum NODE_STATE {OPEN, VISITED, CLOSED};

    public class Dijkstra
    {
        //public List<int> predecessorList = new List<int>();
        public int[] predecessorList;

        class DescendingCompare : IComparer<int>
        {
            public Node[] nodeList;

            public int Compare(int i, int j)
            {
                return (nodeList[j].cost - nodeList[i].cost);
            }
        }


 


	    const int INFINITY = 1000000;

	    // Finds any of v's neighbors
	    void addNeighboursToStack(List<int> openList, bool[,] graph, Node[] nodeList, int v)
	    {
		    for(int i=0; i < nodeList.Length; i++){
			    if(i==v) continue; // don't add self

			    if( graph[v,i] || graph[i,v] )
			    {
                    if (nodeList[i].isOpen && nodeList[i].state == NODE_STATE.OPEN)
				    {
                        nodeList[i].state = NODE_STATE.VISITED;
                        openList.Add(i);

					    int newCost = nodeList[v].cost + 1;
					    if( newCost < nodeList[i].cost )
					    {
						    nodeList[i].cost = newCost;
						    predecessorList[i] = v;
					    }
				    }
			    }
		    }
	    }



        public int[] getPath(bool[,] graph, Node[] nodeList, int start, int goal)
        {
	        if( nodeList.Length < 3 ) return new int[0]; // graph must contain at least 3B

	        // init dijkstra
            for (int i = 0; i < nodeList.Length; i++)
	        {
		        nodeList[i].cost = INFINITY; // initially all nodes are infinitely expensive
                nodeList[i].state = NODE_STATE.OPEN;
                nodeList[i].isOpen = true;
	        }

            predecessorList = new int[nodeList.Length];
	        nodeList[start].cost = 0;

            List<int> openList = new List<int>();
            openList.Add(start);
            DescendingCompare comp = new DescendingCompare();
            comp.nodeList = nodeList;
	        while( openList.Count != 0 )
	        {
                comp.nodeList = nodeList;
                openList.Sort(comp);
                int v = openList[openList.Count - 1];
                openList.RemoveAt( openList.Count-1 );

		        if (v == goal){
                    return predecessorList;
		        }

		        nodeList[v].state = NODE_STATE.CLOSED; // set closed
                nodeList[v].isOpen = false;
		        addNeighboursToStack(openList, graph, nodeList, v);
	        }


            return new int[0]; // return empty if no path
        }
    }

    

 


}
